package com.qch.edu.sort.jiandanSort;

/**
 * @Author qch
 * @Date 2021/3/6
 * 插入排序：稳,O(n^2)，空间O（1）
 *前两个先比较，下标从第二个数开始，第三个数和前面的数比较，如果小和前面交换（类似反向冒泡）
 *
 * 改进：修改算法，用临时变量记录标记项去掉swap方法
 * 要插的数用temp记录a[j]=a[j-1]
 * 还有改进方式：位移
 */

/**
 * 三种简单排序比较
 * 冒泡：基本不用，太慢，每次比较都要交换
 * 选择：基本不用，不稳
 * 插入：三种里最快，样本小企鹅基本有序的时候效率非常高  1，3，5，4，6，7（只要5，4交换就好了）
 */
public class InsertSort {
    public static void main(String[] args) {
        int arr[]={10,9,2,4,5,1,3,8,6,55};
        //int arr[]={10};
        sort(arr);
        print(arr);
    }
    static void sort(int arr[]){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >0&&arr[j]<arr[j-1]; j--) {
                //if(arr[j]<arr[j-1]){
                swap(arr,j,j-1);}
            //}
        }
    }
    static void swap(int[] arr,int i,int minPos)
    {
        int temp=arr[i];
        arr[i]=arr[minPos];
        arr[minPos]=temp;
    }
    static void print(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+",");
        }
    }
}
